package algorithmTopics.string;

public class test7 {

    public static void main(String[] args) {
        test7 test2 = new test7();
        System.out.println(test2.strStr("abc","c"));
    }

    public int strStr(String haystack, String needle) {
        //方法一 Java api自带方法
        //return haystack.indexOf(needle);

        //KMP 算法实现
        // next 数组存贮子串中可以跳过匹配字符的数量
        int[] next = build_next(needle);
        for (int i = 0, j = 0; i < haystack.length(); ) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else if (j > 0) {
                //木有匹配成功，根据next跳过字符
                j = next[j - 1];
            } else {
                // 第一个就不匹配
                i++;
            }
            if (j == needle.length()) {
                //匹配成功,直接返回
                return i - j;
            }

        }
        return -1;
    }

    private int[] build_next(String needle) {
        // 求最长公共前后缀的数量
        // 初始一个0
        int[] next = new int[needle.length()];
        next[0] = 0;
        //当前公共前后缀长度
        int prefix_len = 0;
        for (int i = 1; i < needle.length(); ) {
            if (needle.charAt(prefix_len) == needle.charAt(i)) {
                prefix_len++;
                next[i] = prefix_len;
                i++;
            } else {
                if (prefix_len == 0) {
                    next[i] = prefix_len;
                    i++;
                } else {
                    prefix_len = next[prefix_len - 1];
                }
            }
        }

        return next;
    }
}
